#ifndef UTILS_FOR_SEGMENT_INTERSECTION
#define UTILS_FOR_SEGMENT_INTERSECTION

#include <math.h>
typedef int  BOOL;
#define TRUE 1
#define FALSE 0

#ifndef max
#define max(a, b)            (((a) > (b)) ? (a) : (b))
#endif

#ifndef min
#define min(a, b)            (((a) < (b)) ? (a) : (b))
#endif

#define SIZECOND(a, b) (a + 8 < b)

const int maxStack = 31;
const int Har[10] = {1, 4, 13, 41, 121, 365, 1097, 3293, 9889, 29667};

template<class T> void ssort(T *List, int n)
{
	register int i, j, h;
	int k;
	T temp;
	if (n == 1)
		return;
	for (k = 0; Har[k] < n; k++);
	while (k > 0)
	{
		h = Har[--k];
		for (j = h; j < n; j++)
		{
			temp = List[i = j];
			while ((i >= h) && (temp < List[i - h]))
			{
				List[i] = List[i - h];
				i -= h;
			}
			List[i] = temp;
		}
	}
};

template<class order, class T> void ssort(order &o, T *List, int n)
{
	register int i, j, h;
	int k;
	T temp;
	if (n == 1)
		return;
	for(k = 0; Har[k] < n; k++);
	while (k > 0)
	{
		h = Har[--k];
		for (j = h; j < n; j++)
		{
			temp = List[i = j];
			while ((i >= h) && (o.lt(temp, List[i - h])))
			{
				List[i] = List[i - h];
				i -= h;
			}
			List[i] = temp;
		}
	}
};

template<class T> void fastsort(T *List, int n)
{
	int LStack[maxStack], RStack[maxStack];
	int StackTop;

	int ll, lr, lm, nl, nr;
	T current, temp;

	if (n < 2)
		return;
	ll = 0;
	lr = n - 1;
	StackTop = 0 ;

	while (1)
	{
		while (SIZECOND(ll, lr)) 
		{
			nl = ll;
			nr = lr;
			lm = (ll + lr) >> 1 ;
			current = List[lm];
			// find keys for exchange
			while (1)
			{
				while (List[nl] < current)
					nl++;
				while (current < List[nr])
					nr--;
				if ((nl + 2) > nr)
					break ;
				temp = List[nl];
				List[nl] = List[nr];
				List[nr] = temp;
				nl++;
				nr--;
			}
			if (nl <= nr)
			{
				if (nl <  nr)
				{
					temp = List[nl] ;
					List[nl] = List[nr] ;
					List[nr] = temp ;
				}
				nl++;
				nr--;
			}
			// select sub-list to be processed next
			if (nr < lm)
			{
				LStack[StackTop] = nl;
				RStack[StackTop] = lr;
				lr = nr;
			}
			else
			{
				LStack[StackTop] = ll;
				RStack[StackTop] = nr;
				ll = nl;
			}
			StackTop++;
		}; //  while (ll < lr) 
		ssort(List + ll, lr - ll + 1);

		if (StackTop == 0)
			return;
		StackTop-- ;
		ll = LStack[StackTop] ;
		lr = RStack[StackTop] ;
	}
}

template<class order, class T> void fastsort(order &o, T *List, int n)
{
	int LStack[maxStack], RStack[maxStack];
	int StackTop;

	int ll, lr, lm, nl, nr;
	T current, temp;

	if (n < 2)
		return;
	ll = 0;
	lr = n - 1;
	StackTop = 0 ;

	while (1)
	{
		while (SIZECOND(ll, lr)) 
		{
			nl = ll;
			nr = lr;
			lm = (ll + lr) >> 1 ;
			current = List[lm];
			while (1)
			{
				while (o.lt(List[nl], current))
					nl++;
				while (o.lt(current, List[nr]))
					nr--;
				if ((nl + 2) > nr)
					break;
				temp = List[nl];
				List[nl] = List[nr];
				List[nr] = temp;
				nl++;
				nr--;
			}
			if (nl <= nr)
			{
				if (nl < nr)
				{
					temp = List[nl] ;
					List[nl] = List[nr] ;
					List[nr] = temp ;
				}
				nl++;
				nr--;
			}
			if (nr < lm)
			{
				LStack[StackTop] = nl;
				RStack[StackTop] = lr;
				lr = nr;
			}
			else
			{
				LStack[StackTop] = ll;
				RStack[StackTop] = nr;
				ll = nl;
			}
			StackTop++;
		};  
		ssort(o, List + ll, lr - ll + 1);

		if (StackTop == 0)
			return;
		StackTop-- ;
		ll = LStack[StackTop];
		lr = RStack[StackTop];
	}
}

template<class T> 
class tuple{
public:
	T x;
	T y;
	tuple()
	{
		x = 0;
		y = 0;
	}
	tuple(const T &xc, const T &yc) :
		x(xc),
		y(yc)
	{};
	int operator<(tuple<T> &v2)
	{
		return ((x < v2.x)||(x == v2.x) && (y < v2.y));
	};
	int operator>(tuple<T> &v2)
	{
		return ((x > v2.x)||(x == v2.x) && (y > v2.y));
	};
	tuple<T> operator-()
	{
		return tuple<T>(-x, -y);
	};
	T get_norm()
	{
		return x*x + y*y;
	}
	T get_length()
	{
		return sqrt(x*x + y*y);
	};
	tuple<T>& normalize()
	{
		T l = get_length();
		x /= l;
		y /= l;
		return *this;
	};
	tuple<T> get_normalized()
	{
		T l = get_length();
		return tuple<T>(x/l, y/l);
	};
};

template <class T> inline T operator%(tuple<T> v1, tuple<T> v2)
{return v1.x*v2.y - v2.x*v1.y;}

template <class T> inline tuple<T> operator*(const T &r, tuple<T> &t)
{return tuple<T>(t.x * r, t.y * r);}

template <class T> inline tuple<T> operator*(tuple<T> &t, T &r)
{return tuple<T>(t.x * r, t.y * r);}

template <class T> inline T operator*(tuple<T> t, tuple<T> v)
{return t.x*v.x + t.y*v.y;}

template <class T> inline tuple<T> operator+(tuple<T> &v1, tuple<T> &v2)
{return tuple<T>(v1.x + v2.x, v1.y + v2.y);}

template <class T> inline tuple<T> operator-(tuple<T> &v1, tuple<T> &v2)
{return tuple<T>(v1.x - v2.x, v1.y - v2.y);}


class CRandomValueGen
{
public:
	double GetRandomDouble();
	BOOL RandomChoose();
};

typedef tuple<double> TPlaneVect;
#endif